1884E - Hard Design - CodeForces Solution

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int a[3000005];
long long cost[3000005],mod=1e9+7;
long long cnt[3000005],ans1[1000005],ans2[1000005];
int main() {
    int T = 1, kase = 0;
    cin >> T;
    while (T--) {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i+n*2]=a[i];
        int mx=0,p=-1;
        for(int i=n+1;i<=n*2;i++) if(a[i]>mx) mx=a[i],p=i;
        cost[p]=cnt[p]=0;
        long long c=a[p],s=0;
        vector <int> stk;
        stk.push_back(p);
        for(int i=p-1;i>p-n;i--){
            cost[i]=cost[i+1],cnt[i]=cnt[i+1];
            if(a[i]<a[stk.back()]) cnt[i]+=a[stk.back()]-a[i];
            int lst=0;
            while(stk.size()&&a[i]>=a[stk.back()]){
                c-=a[stk.back()]-lst,s-=1LL*(a[stk.back()]-lst)*(stk.back()-i-1);
                lst=a[stk.back()],stk.pop_back();
            }
            if(stk.size()){
                c-=a[i]-lst,s-=1LL*(a[i]-lst)*(stk.back()-i-1);
            }
            //cout<<c<<" "<<s<<endl;
            cost[i]=(cost[i]+s*2+c)%mod;
            s+=c,c+=a[i],stk.push_back(i);
            //cout<<cost[i]<<" "<<cnt[i]<<" "<<c<<" "<<s<<endl;
        }
        stk.clear(),c=a[p],s=0;
        stk.push_back(p);
        for(int i=p+1;i<p+n;i++){
            cost[i]=cost[i-1],cnt[i]=cnt[i-1];
            if(a[i]<a[stk.back()]) cnt[i]+=a[stk.back()]-a[i];
            int lst=0;
            while(stk.size()&&a[i]>=a[stk.back()]){
                c-=a[stk.back()]-lst,s-=1LL*(a[stk.back()]-lst)*(i-stk.back()-1);
                lst=a[stk.back()],stk.pop_back();
            }
            if(stk.size()){
                c-=a[i]-lst,s-=1LL*(a[i]-lst)*(i-stk.back()-1);
            }
            //cout<<c<<" "<<s<<endl;
            cost[i]=(cost[i]+s*2+c)%mod;
            s+=c,c+=a[i],stk.push_back(i);
            //cout<<cost[i]<<" "<<cnt[i]<<" "<<c<<" "<<s<<endl;
        }
        for(int i=p-n+1;i<=p;i++) ans1[(i-1)%n]=cnt[i]+cnt[i+n-1],ans2[(i-1)%n]=(cost[i]+cost[i+n-1])%mod;
        for(int i=0;i<n;i++) printf("%lld %lld\n",ans1[i],ans2[i]);
    }
    return 0;
}